package com.github.tangmonkmeat;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/2/7 11:49
 */
public class 零钱兑换 {

    static int[] ss;

    public static void main(String[] args) {

        List<Integer> a = new ArrayList<>();
        a.add(1);
        Object[] objects = a.toArray();
        System.out.println(objects[0]);

        //int num = new 零钱兑换().coinChange2(new int[]{1,2,5}, 5);
        // System.out.println(num);

        //int num = new 零钱兑换().coinChange2(new int[]{1, 2, 3}, 2);
        //System.out.println(num);
    }

    public int coinChange2(int[] coins, int amount) {
        // 自底向上的动态规划
        if(coins.length == 0){
            return -1;
        }
        // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
        int[] memo = new int[amount+1];
        memo[0] = 0;
        for(int i = 1; i <= amount;i++){
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i - coin >= 0 && memo[i - coin] < min) {
                    min = memo[i - coin] + 1;
                }
            }
            memo[i] = min;
        }

        return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
    }


    int res = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        if (coins.length < 1) {
            return -1;
        }
        def(coins, amount, 0);
        // 一个组合都没有找到，返回 -1
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public void def(int[] coins, int amount, int count) {
        // 当前的硬币值太大
        if (amount < 0) {
            return;
        }
        // 找到一种组合
        else if (amount == 0) {
            res = Math.min(res, count);
            return;
        }
        for (int coin : coins) {
            def(coins, amount - coin, count + 1);
        }
    }


}
